package com.lwl.Algorithmic_data_structure.归并排序;

import org.junit.Test;

public class P327_countRangeSum {
    /**
     * 给你一个整数数组 nums 以及两个整数 lowwer 和 upper 。求数组中，值位于范围 [lowwer, upper]
     * （包含 lowwer 和 upper）之内的 区间和的个数 。
     * 区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
     */
    public int countRangeSum(int[] nums, int lower, int upper) {
        //思路 ： 先使用前缀数组优化求和,“此后操作的都是前缀和”,使用归并的思路的去操作
        //因为 左部和右部都是有序的前缀和，所以可以做到不回退的效果
        //先清楚 右部元素 - 左部元素 得到是一个范围的数组和，因为右部的坐标永远是比左部坐标大的(左部和右部的内部是经过排序得到有序的前缀和元素)
        //求 ：右部元素 - 左部元素 ∈ [lowwer,upper] ==> 左部元素 ∈ [右部元素 - upper,右部元素 - lowwer]
        //注意 ： 这里的元素都是指的前缀和元素
        long[] sums = new long[nums.length];
        sums[0] = nums[0];
        for (int i = 1; i < sums.length; i++) {
            sums[i] = sums[i-1] + nums[i];
        }
        return process(sums,0,sums.length-1,lower,upper);
    }

    private int process(long[] sums, int left, int right, int lower, int upper) {
        if (left == right){//这里不是说只有一个元素，而是相当于左部为空，判断【0，left/right】的前缀和
            return sums[left] >= lower && sums[right] <= upper ? 1 : 0;
        }
        int mid = left + (right-left)/2;
        int p1 = process(sums, left, mid, lower, upper);
        int p2 = process(sums, mid+1, right, lower, upper);
        return p1 + p2 + merge(sums,left,mid,right,lower,upper);
    }

    private int merge(long[] sums, int left, int mid, int right, int lower, int upper) {
        int res = 0;
        //这个窗口是在左部中变化的
        int windowL = left;
        int windowR = left;
        for (int i = mid+1; i <= right; i++) {
            long min = sums[i] - upper;
            long max = sums[i] - lower;
            //注意 左部前缀和元素此时已经是有序的，此刻记得这是基于归并排序的！
            while (windowL <= mid && sums[windowL] < min){
                windowL++;
            }
            while (windowR <= mid && sums[windowR] <= max){
                windowR++;
            }
            //因为windowR对应的元素是大于 upper的，所以取的数量应该是 【windowL,windowR)，左闭右开
            res += windowR - windowL;
        }
        //接下来就是归并排序了，为了下一次的merge左部和右部是有序的
        long[] help = new long[right - left + 1];
        int l = left,r = mid+1;
        int index = 0;
        while (l <= mid && r <= right){
            help[index++] = sums[l] <= sums[r] ? sums[l++] : sums[r++];
        }
        while (l <= mid){
            help[index++] = sums[l++];
        }
        while (r <= right){
            help[index++] = sums[r++];
        }
        index = 0;
        for (int i = left; i <= right; i++) {
            sums[i] = help[index++];
        }
        return res;
    }
    @Test
    public void test(){
        System.out.println(countRangeSum(new int[]{-2, 5, -1}, -2, 2));
    }
}
